package server.simple100;

import org.junit.Test;

/***
 * 108. 将有序数组转换为二叉搜索树
 */
public class LeetCode108 {


    @Test
    public void test() {
        int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        TreeNode treeNode = sortedArrayToBST(nums);
        System.out.println(treeNode);
    }


    public TreeNode sortedArrayToBST(int[] nums) {
        // 开始递归设置值
        return nextNode(nums, 0, nums.length - 1);
    }


    /**
     * @param nums       原始数据
     * @param leftIndex  左边界
     * @param rightIndex 右边界
     * @return void
     * @author wangsong
     * @date 2022/4/6 13:43
     */
    public TreeNode nextNode(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex > rightIndex) {
            return null;
        }

        // 1、获取每一级的 中间值 为当前节点的值（获取二分后索引，通过索引获取值）
        int mid = leftIndex + (rightIndex - leftIndex) / 2;
        TreeNode treeNode = new TreeNode(nums[mid]);

        // 2、根据每一级的中间值 往左边 进行递归 (递归重复 1-2-3 步骤)
        treeNode.left = nextNode(nums, leftIndex, mid - 1);

        // 3、根据每一级的中间值 往右边 进行递归 (递归重复 1-2-3 步骤)
        treeNode.right = nextNode(nums, mid + 1, rightIndex);

        return treeNode;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
//    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
//
//        高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
//
//         
//
//        示例 1：
//
//
//        输入：nums = [-10,-3,0,5,9]
//        输出：[0,-3,9,-10,null,5]
//        解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
//        示例 2：
//
//
//        输入：nums = [1,3]
//        输出：[3,1]
//        解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
//         
//
//        提示：
//
//        1 <= nums.length <= 104
//        -104 <= nums[i] <= 104
//        nums 按 严格递增 顺序排列
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。